package graph;

import list.Stack;

/**
 * description:
 * author:张腾
 * date:2021-04-13
 */

/**
 * 使用深度优先搜索实现路径查找
 */
public class DeptFirstPaths {

    //索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    //起点
    private int s;
    //索引代表顶点，值代表从起点到当前顶点路径上的最后一个顶点
    private int[] edgeTo;

    //使用深搜搜索出以s为起点的所有路径
    public DeptFirstPaths(Graph g,int s){
        this.marked = new boolean[g.V()];
        this.s = s;
        this.edgeTo = new int[g.V()];
    }

    //使用深搜找出g图中v顶点所有相通的顶点
    private void dfs(Graph g,int v){
        marked[v] = true;

        //遍历v的邻接表，每拿到一个相邻的顶点则递归调用dfs
        for (Integer w : g.adj(v)) {

            if (!marked[w]){
                //到达顶点w的路径上，最后一个顶点是v
                edgeTo[w] = v;
                dfs(g,w);
            }
        }
    }

    //判断起点到顶点v是否有路径
    public boolean hasPathTo(int v){

        return marked[v];
    }

    //找出从起点到顶点v的路径
    //用栈存路径，因为edgeTo存的是上一个顶点，所以方向是从终点往起点存，则最后取路径时就是从起点开始
    public Stack<Integer> pathTo(int v){

        if (!hasPathTo(v)){
            return null;
        }
        Stack<Integer> path = new Stack<>();

        for(int x = v;x != s; x = edgeTo[x]){
            path.push(x);
        }
        //再把起点放入栈中
        path.push(s);

        return path;
    }

}
